package Tree;

import java.util.ArrayList;
import java.util.List;

public class 另一棵树的子树 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        List<TreeNode> list = new ArrayList<>();
        preorder(root, list, subRoot.val);
        boolean flag = false;
        for (TreeNode treeNode : list) {
            flag = isSameTree(treeNode, subRoot);
            if (flag) break;
        }
        return flag;
    }

    private List<TreeNode> preorder(TreeNode root, List<TreeNode> list, int target) {
        if (root == null) return list;
        if (root.val == target) list.add(root);
        preorder(root.left, list, target);
        preorder(root.right, list, target);
        return list;
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null) return q == null;
        else if (q == null) return false;
        else if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
